

'''
时间复杂度：最坏：O(n^2) 最好：根据步长序列的不同而不同 平均：O(n^1.3)
空间复杂度：O(1)
稳定性：不稳定
'''
def shell_sort(nums):
    n = len(nums)
    gap = n//2
    while gap > 0:
        for j in range(gap,n):
            i = j
            while i>0:
                if nums[i] < nums[i-gap]:
                    nums[i],nums[i-gap] = nums[i-gap],nums[i]
                    i -= gap
                else:
                    break
        gap//=2

nums = [5,4,3,2,1]
shell_sort(nums)
print(nums)


def shell_sort2(nums):
    n = len(nums)
    gap = n//2
    while gap >0:
        for j in range(gap,n):
            i = j
            while i > 0 :
                if nums[i] < nums[i-gap]:
                    nums[i],nums[i-gap] = nums[i-gap],nums[i]
                    i -= gap
                else:
                    break
        gap//=2